package hard;

import java.util.Arrays;

/**
 * 1542. 找出最长的超赞子字符串
 *
 * @date 2024/5/20 18:45
 * 地址：https://leetcode.cn/problems/find-longest-awesome-substring/description/?envType=daily-question&envId=2024-05-20
 **/
public class 找出最长的超赞子字符串_1542 {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestAwesome("12345678"));
    }

    static class Solution {
        public int longestAwesome(String s) {
            int sort = 10;
            int[] pos = new int[1 << sort];
            Arrays.fill(pos, -2);
            pos[0] = -1;
            int ans = 0;
            int stat = 0;
            int n = s.length();
            for (int i = 0; i < n; i++) {
                stat ^= 1 << (s.charAt(i) - '0'); //计算出现次数（状态压缩）
                if (pos[stat] != -2) {
                    ans = Math.max(ans, i - pos[stat]);
                } else {
                    pos[stat] = i;
                }
                for (int j = 0; j < sort; j++) {
                    ans = Math.max(ans, i - pos[stat ^ (1 << j)]);
                }
            }
            return ans;
        }
    }
}
